/**
 * 174. 地下城游戏
 * https://leetcode-cn.com/problems/dungeon-game/
 */
public class Solutions_174 {
    public static void main(String[] args) {
        int[][] dungeon = {{-2, -3, 3},
                           {-5, -10, 1},
                           {10, 30, -5}};  // output: 7

//        int[][] dungeon = {{-1, 1}};  // output: 2

//        int[][] dungeon = {{100}};  // output: 1

        int result = calculateMinimumHP(dungeon);
        System.out.println(result);
    }

    public static int calculateMinimumHP(int[][] dungeon) {
        if (dungeon == null || dungeon.length < 1 || dungeon[0].length < 1) {
            return 0;
        }
        int row = dungeon.length, col = dungeon[0].length;
        // dp[0][0] = 7，表示从 [0, 0] 到达 [row - 1, col - 1] 位置，最少的初始健康点数
        int[][] dp = new int[row + 1][col + 1];
        // 设置默认值 1，因为健康点数在某一时刻降至 0 或以下，他会立即死亡，所以最少需要 1 个点数
        dp[row][col - 1] = dp[row - 1][col] = 1;

        for (int i = row - 1; i >= 0; i--) {
            for (int j = col - 1; j >= 0; j--) {
                // 当前房间可以获得的 hp
                int curhp = dungeon[i][j];

                if (i == row - 1) {
                    // 右侧：只能从右侧走来
                    dp[i][j] = -curhp + dp[i][j + 1];
                } else if (j == col - 1) {
                    // 下方：只能从下边走来
                    dp[i][j] = -curhp + dp[i + 1][j];
                } else {
                    // 选择最小值（最优路径）
                    dp[i][j] = -curhp + Math.min(dp[i][j + 1], dp[i + 1][j]);
                }
                if (dp[i][j] <= 0) {
                    // 关键：计算后，若 dp[i][j] <= 0，说明在当前房间可以获得足够的 hp 到达终点
                    // 那么只需要带 1 个点数进入即可
                    dp[i][j] = 1;
                }
            }
        }
        return dp[0][0];
    }
}
